package my.sort.cmp;

import my.sort.Sort;

/**
 * 堆排序
 *
 * @author AJun
 * @date 2020/9/15
 */
public class HeapSort<T extends Comparable<T>> extends Sort<T> {

    /**
     * 堆大小
     */
    private int heapSize;

    @Override
    protected void sort() {
        // 原地建堆，自下而上的下滤，推荐这种，效率较高 O(n)
        heapSize = array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }

        while (heapSize > 1) {
            // 交换堆顶和尾部元素
            swap(0, --heapSize);
            // 对 0 位置元素进行 siftDown(恢复堆的性质)
            siftDown(0);
        }
    }

    /**
     * 让 index 位置的元素下滤
     *
     * @param index 元素索引
     */
    private void siftDown(int index) {
        T element = array[index];
        int half = heapSize >> 1; // 公式
        // 必须保证 index 位置是非叶子节点，第一个叶子节点的索引就是非叶子节点的数量
        while (index < half) {
            // 默认使用左子节点和要删除的元素进行比较
            int childIndex = (index << 1) + 1; // 公式
            T child = array[childIndex];
            // 右子节点
            int rightIndex = childIndex + 1;
            // 选出左右子节点最大的
            if (rightIndex < heapSize && cmp(array[rightIndex], child) > 0)
                child = array[childIndex = rightIndex];
            // 要删除元素大于子节点元素
            if (cmp(element, child) >= 0)
                break;

            // 要删除元素小于子节点元素，将子节点存放到 index 位置
            array[index] = child;
            // 重新对 index 赋值
            index = childIndex;
        }
        array[index] = element;
    }

}
